package P912;

import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/2/28 8:21
 * @Version 1.0
 * @Name 排序数组
 * @Problem https://leetcode-cn.com/problems/sort-an-array/
 * 归并排序
 * 了解到java中传入数组和c++中的引用一样
 * 参考：https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/
 */
public class Solution4 {
    @Test
    public void test(){
        for (int i : sortArray(new int[]{5, 2})) {
            System.out.println(i);
        }
        return;
    }
    public int[] sortArray(int[] nums) {
        int[] temp  = new int[nums.length];
        sort(nums,0,nums.length,temp);
        return nums;
    }
    void sort(int[] nums,int left,int right,int[] temp) {
        if(left+1==right){//只有一个元素 出口
            return ;
        }
        //分解
        int mid =left+((right-left)>>1);
        sort(nums,left,mid,temp);//[left,mid)
        sort(nums,mid,right,temp);//[mid,right)
        //如果两个子区间本身就有序，就无需合并
        if(nums[mid-1]<nums[mid]){
            return;
        }
        merge(nums,left,mid,right,temp);
    }

    void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid;
        int k = 0;
        while(i<mid&&j<right){
            if(nums[i]>nums[j]){
                temp[k++]=nums[j++];
            }else{
                temp[k++]=nums[i++];
            }
        }
        while(i<mid){
            temp[k++] = nums[i++];
        }
        while(j<right){
            temp[k++] = nums[j++];
        }
        for (int l = 0; l < right-left; l++) {
            nums[left+l] = temp[l];
        }
    }
}
